<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    116. Populating Next Right Pointers in Each Node
   </h1>
   <p>
    You are given a
    <strong>
     perfect binary tree
    </strong>
    &nbsp;where&nbsp;all leaves are on the same level, and every parent has two children. The binary tree has the following definition:
   </p>
   <pre>
struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
</pre>
   <p>
    Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to
    <code>
     NULL
    </code>
    .
   </p>
   <p>
    Initially, all next pointers are set to
    <code>
     NULL
    </code>
    .
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Example:
    </strong>
   </p>
   <p>
    <img alt="" src="https://assets.leetcode.com/uploads/2019/02/14/116_sample.png" style="width: 640px; height: 218px;">
   </p>
   <pre>
<strong>Input: </strong><span>{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}</span>

<strong>Output: </strong><span>{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}</span>

<strong>Explanation: </strong>Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ul>
    <li>
     You may only use constant extra space.
    </li>
    <li>
     Recursive approach is fine, implicit stack space does not count as extra space for this problem.
    </li>
   </ul>
  </div>
  <div>
   <h1 class="question_title">
    116. 填充每个节点的下一个右侧节点指针
   </h1>
   <p>
    给定一个
    <strong>
     完美二叉树
    </strong>
    ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
   </p>
   <pre>struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}</pre>
   <p>
    填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为
    <code>
     NULL
    </code>
    。
   </p>
   <p>
    初始状态下，所有&nbsp;next 指针都被设置为
    <code>
     NULL
    </code>
    。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例：
    </strong>
   </p>
   <p>
    <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/15/116_sample.png" style="height: 218px; width: 640px;">
   </p>
   <pre><strong>输入：</strong>{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

<strong>输出：</strong>{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

<strong>解释：</strong>给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ul>
    <li>
     你只能使用常量级额外空间。
    </li>
    <li>
     使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
    </li>
   </ul>
  </div>
 </body>
</html>